#include <cstdio>
#include <cstring>
#include <iostream>
#include <algorithm>
#include <vector>
#include <cmath>
#include <queue>
#include <set>

#define flr(x,l,r) for (int x = l; x <= r; ++ x)
#define frl(x,r,l) for (int x = r; x >= l; -- x)
#define fmp(x,t) for (int x = h[t]; ~x; x = ne[x])
#define LL long long 
#define mt memset 
#define szf sizeof
#define INF 0x3f3f3f3f
#define in(x) scanf("%d", &x)
#define out(x) printf("%d", x)
#define inll(x) scanf("%lld", &x)
#define outll(x) printf("%lld", x)
#define pn printf("\n")
#define con continue
#define bk break
#define vc vector
#define pb push_back
#define sz size
#define PII pair<int, int>
#define x first
#define y second
#define P_q priority_queue
#define ft front
#define pf push_front
#define popf pop_front
#define it insert
#define ct count

using namespace std;

const int N = 15, M = 400, P = 1 << 10;

int n, m, p, k;
int h[N * N], e[M], w[M], ne[M], idx;
int g[N][N], key[N * N];
int dist[N * N][P];
bool st[N * N][P];

set<PII> edge;

void add(int a, int b, int c) {
    e[idx] = b, w[idx] = c, ne[idx] = h[a], h[a] = idx ++ ;
}

void build() {
    int dx[4] = {-1, 0, 1, 0}, dy[4] = {0, -1, 0, 1};
    
    flr (i, 1, n)
        flr (j, 1, m)
            flr (u, 0, 3) {
                int x = i + dx[u], y = j + dy[u];
                if (!x || x > n || !y || y > m) con;
                int a = g[i][j], b = g[x][y];
                if (edge.ct({a, b}) == 0) add(a, b, 0);
            }
}

int bfs() {
    mt(dist, 0x3f, szf dist);
    dist[1][0] = 0;
    
    deque<PII> q;
    q.push_front({1, 0});
    
    while (q.size()) {
        PII t = q.ft();
        q.popf();
        
        if (st[t.x][t.y]) con;
        st[t.x][t.y] = true;
        
        if (t.x == n * m) return dist[t.x][t.y];
        
        if (key[t.x]) {
            int state = t.y | key[t.x];
            if (dist[t.x][state] > dist[t.x][t.y]) {
                dist[t.x][state] = dist[t.x][t.y];
                q.pf({t.x, state});
            }
        }
        
        fmp (i, t.x) {
            int j = e[i];
            if (w[i] && !(t.y >> w[i] - 1 & 1)) con;
            if (dist[j][t.y] > dist[t.x][t.y] + 1) {
                dist[j][t.y] = dist[t.x][t.y] + 1;
                q.pb({j, t.y});
            }
        }
    }
    
    return -1;
}

int main() {
	cin >> n >> m >> p >> k;
	
	int t = 1;
	flr (i, 1, n) 
	    flr (j, 1, m)
	        g[i][j] = t ++ ;
	
	mt(h, -1, szf h);
	while (k -- ) {
	    int x1, y1, x2, y2, c;
	    cin >> x1 >> y1 >> x2 >> y2 >> c;
	    int a = g[x1][y1], b = g[x2][y2];
	    edge.it({a, b}), edge.it({b, a});
	    if (c) add(a, b, c), add(b, a, c);
	}
	
	build();
	
	int num;
	in(num);
	while (num -- ) {
	    int x, y, id;
	    cin >> x >> y >> id;
	    key[g[x][y]] |= 1 << id - 1;
	}
	
	out(bfs()), pn;
	
	return 0;
}